mod Pでの逆元

フェルマーの小定理

$ a^{p-1}\equiv 1{\pmod {p}}

を変形して

$ a \times a^{p-2}\equiv 1{\pmod {p}}

なので

$ a^{-1} \equiv a^{p-2} {\pmod {p}}

フェルマーの小定理はPが素数であることを要求する

この場合はaとpが互いに素であれば良い

code:python

def mod_inverse_ee(a, m):

"""

Solve ax mod m = 1 with extended euclidean.

x = a^-1.

"""

x, y, g = extended_euclidean(a, m)

assert g == 1

return x % m

pow(n, p-2, p)